Intersymbol interference is a recognised problem resulting from transmission of data on a dispersive communication channel and an equalisation process is effected on the received signal in order to estimate the individual data symbols which were originally transmitted. Various types of equaliser are known but of particular interest in the present context are so-called maximum likelihood (ML) detectors.
Furthermore, for the purpose of forward error correction, data may be convolutionally encoded before it is transmitted. (Forward error correction means that the data is corrected at the receiver without the need for retransmission.) A ML detector may also be used for decoding convolutionally encoded data.
In the context of ML detection, a trellis diagram is commonly used to represent the progression of states with the passage of time. It is noted here that the number of states S is given by the equation S=N.sup.c where N is the number of symbols in the data alphabet used and C is the constraint length (i.e. extent of intersymbol interference). Thus for a 2-symbol alphabet and a constraint length of 4 there are 16 possible states.
The term `node` is usually used to designate a particular state at a particular time on a trellis diagram.
The arc or path representing the transition between two states (nodes) adjacent in time is known as a `branch` and the associated `branch metric` is an indication of the likelihood of the particular transition occurring. The `partial path metric` is the overall probability that a particular partial path to the left of the node at the current stage n of the trellis represents the correct sequence of state transitions, taking into account the observed sample of the received data at the current trellis transition and the branch metric. The term `partial path` is construed accordingly. This is the meaning of the terms partial path and partial path metric as they are used in the present specification, but the terms `path` and `path metric` are also used to convey the same meaning. The `previous partial path metric` thus refers to the path metric at the previous stage n-1 of the trellis. The overall path i.e. the path between the beginning and the end of the trellis which has the maximum path metric is the maximum likelihood path which essentially represents the best estimate of the data symbols actually transmitted.
In theory a maximum likelihood (ML) or maximum a-posteriori (MAP) detector may be used wherein the branch metrics are calculated for every branch in the trellis diagram. The path metric for every path in the trellis diagram is then determined, and finally the path for which the overall path metric is a maximum is chosen. The sequence of symbols corresponding to this path is the estimate of the symbols actually transmitted. The difficulty with this approach is that the number of paths increases exponentially as the trellis diagram is traversed from left to right.
The so-called Viterbi detector is a computationally more efficient version of a ML detector which exploits the special structure of the detector to achieve a complexity that grows linearly rather than exponentially along the trellis. Hence, a Viterbi detector has the advantage that it requires a constant computation rate per unit time. For each node, the Viterbi detector selects the path having the largest partial path metric, called the `survivor path` for that node. All partial paths other than the survivor path are discarded because any other partial path has by definition a smaller partial path metric, and hence if it replaced the survivor path in any overall path, the path metric would be smaller.
At each stage of the trellis it is not known which node the optimal path must pass through and so it is necessary to retain one survivor path for each and every node. The survivor path and associated path metric have to be stored in memory for each node at a stage n in the trellis in order for the algorithm to proceed to the next stage n+1.
When the terminal node of the trellis has been reached it is possible to determine the unique path of maximum likelihood representing the estimation of the symbols actually transmitted. It is only at this stage that the estimated data symbols can be read off by effecting a "trace-back" along the identified maximum likelihood path.
Despite its improved efficiency mentioned above, it has to be noted the Viterbi algorithm remains intrinsically computationally elaborate and therefore the processing circuitry for implementing the algorithm tends to be complex, costly and power consuming. Furthermore, the level of complexity means that a substantial area of semiconductor material is required for realization of a conventional Viterbi detector in integrated circuit (IC) form.
European Patent Application No. 0,398,690, which was published after the priority date of the subject application, relates to circuitry for implementing the Viterbi algorithm, wherein the states of the bits of a defined time interval are processed utilizing the circuitry in serial form for indicating the data symbol.